package main

import (
	"fmt"
	"image"
	"image/color"
	"image/png"
	"math/rand"
	"os"
	"time"

	"github.com/nfnt/resize"
)

/**
讲述迷宫生成算法:https://zhuanlan.zhihu.com/p/27381213
**/
func main() {
	l := newLabyrinth(13, 18)
	//l.createPlan0("plan0.png")
	//l.findWay("plan0_f.png")
	//
	//l.createPlan1("plan1.png")
	//l.findWay("plan1_f.png")

	l.createPlan2("plan2.png")
	l.findWay("plan2_f.png")
}

const (
	up    dir = 1
	down  dir = 2
	left  dir = 4
	right dir = 8

	dataZero  data = 0 // 初始化0
	dataOne   data = 1 // 初始化1
	dataTwo   data = 2 // 迷宫的路径
	dataThree data = 3 // 迷宫起始位置
	dataFour  data = 4 // 迷宫结束位置
	dataFive  data = 5 // 迷宫解的位置
	dataSix   data = 6 // 橙色1
)

type (
	dir  int
	data int

	pot struct {
		row, col, cnt int // 该点所在行列,方向个数
		dir           dir // 找路时需要的方向
	}

	path struct {
		path []pot // 缓存过程中需要用到的内容
		cur  int   // 当前迷宫生成到哪个位置
	}

	labyrinth struct {
		row, col   int      // 迷宫的行列数
		data       [][]data // 迷宫的二维数组数据
		path       path     // 迷宫路径
		start, end pot      // 保存迷宫起点和终点
	}
)

// 初始化对象,传入row,col为初始1的行列数
func newLabyrinth(row, col int) *labyrinth {
	row, col = row*2+1, col*2+1 // 得到实际行列
	l := &labyrinth{
		row: row, col: col,
		path: path{path: make([]pot, row*col)}, // 存迷宫路径数据
		data: make([][]data, row),              // 二维数据生成行
	}
	for i := 0; i < row; i++ { // 二维数据每行生成列
		l.data[i] = make([]data, col)
	}
	rand.Seed(time.Now().UnixNano())
	return l
}

// 初始化各项数据,按照方案1去初始化
func (c *labyrinth) initPlan1() {
	for i := 0; i < c.row; i++ {
		for j := 0; j < c.col; j++ {
			if i&1 == 1 && j&1 == 1 {
				c.data[i][j] = dataOne // 奇数行,奇数列置为1
			} else {
				c.data[i][j] = dataZero
			}
		}
	}
	c.path.cur = 0 // path当前位置为0
}

// 初始化各项数据,按照方案2去初始化
// 初始化块状算法不算太好,但是我也不想费神去优化了
func (c *labyrinth) initPlan2() {
	c.initPlan1() // 先初始化成方案1的情况
	// 随机[10,16)个块状
	for i := rand.Intn(6) + 10; i >= 0; i-- {
		// 块状宽高随机[3,5]
		w, h := rand.Intn(2)*2+3, rand.Intn(2)*2+3
		// 找到合适左上角顶点,将这一块写成橙色1,cntFind避免一直找不到
		for cntFind := 0; cntFind < 100; cntFind++ {
			x, y := rand.Intn(c.row/2)*2+1, rand.Intn(c.col/2)*2+1
			if x < 2 || y < 2 || x+w+1 >= c.col || y+h+1 >= c.row {
				continue // 超过边界的顶点不考虑
			}

			flag := true
			for ix := -1; ix <= w; ix++ {
				if c.data[y-2][x+ix] == dataSix || c.data[y+h+1][x+ix] == dataSix {
					flag = false
					break
				}
			}
			if !flag {
				continue
			}
			for iy := -1; iy <= h; iy++ {
				if c.data[y+iy][x-2] == dataSix || c.data[y+iy][x+w+1] == dataSix {
					flag = false
					break
				}
			}
			if !flag {
				continue
			}

			for ix := 0; ix < w; ix++ {
				for iy := 0; iy < h; iy++ {
					c.data[y+iy][x+ix] = dataSix
				}
			}
			break
		}
	}
}

// 将迷宫数据写入png图片,直观的感受迷宫情况
func (c *labyrinth) writeDataPng(pngFile string) error {
	buf := make([]uint8, 4*c.col*c.row)
	for i := 1; i < len(buf); i += 4 {
		buf[i], buf[i+2] = 0xFF, 0xFF
	}
	img := &image.RGBA{ // 得到一张纯绿色图片的信息
		Pix:    buf,
		Stride: 4 * c.col,
		Rect:   image.Rect(0, 0, c.col, c.row),
	}
	cZero := color.RGBA{R: 43, G: 43, B: 43, A: 0xFF}
	cFive := color.RGBA{R: 227, G: 231, B: 48, A: 0xFF} // 使用频繁,因此提出来
	for y := 0; y < c.row; y++ {
		for x := 0; x < c.col; x++ {
			switch c.data[y][x] {
			case dataZero: // 围墙
				img.SetRGBA(x, y, cZero)
			case dataFive: // 迷宫解的点
				img.SetRGBA(x, y, cFive)
			}
		}
	}
	// 起始点置为红色
	img.SetRGBA(c.start.col, c.start.row, color.RGBA{R: 0xFF, G: 0, B: 0, A: 0xFF})
	// 结束点置为蓝色
	img.SetRGBA(c.end.col, c.end.row, color.RGBA{R: 0, G: 0, B: 0xFF, A: 0xFF})

	fw, err := os.Create(pngFile)
	if err != nil {
		return err
	}
	defer fw.Close()
	rw, rh := uint(c.col*20), uint(c.row*20) // 保存的图片放大20倍
	return png.Encode(fw, resize.Resize(rw, rh, img, resize.NearestNeighbor))
}

// 将迷宫数据写入文件,方便查看迷宫生成后的数据
func (c *labyrinth) writeDataFile(outFile string) {
	fw, err := os.Create(outFile)
	if err != nil {
		panic(err)
	}
	defer fw.Close()

	for j := 0; j < c.col-1; j++ {
		fmt.Fprintf(fw, "%02d ", j)
	}
	fmt.Fprintln(fw)
	for i := 1; i < c.row-1; i++ {
		fmt.Fprintf(fw, "%02d", i)
		for j := 1; j < c.col-1; j++ {
			if c.data[i][j] > 0 {
				fmt.Fprintf(fw, " %d ", c.data[i][j])
			} else {
				fmt.Fprint(fw, "   ")
			}
		}
		fmt.Fprintln(fw)
	}
}

// 找到迷宫的解
func (c *labyrinth) findWay(outPng string) {
	findDir := func(p int) (int, dir) {
		var (
			cnt, mDir = 0, dir(0)
			p1        = c.path.path[p]
			p2        = pot{}
			pt        = map[dir]pot{
				up:    {row: p1.row - 1, col: p1.col}, // 向上
				down:  {row: p1.row + 1, col: p1.col}, // 向下
				left:  {row: p1.row, col: p1.col - 1}, // 向左
				right: {row: p1.row, col: p1.col + 1}, // 向右
			}
		)

		if p > 0 { // 不能找原路的方向
			p2 = c.path.path[p-1]
		}

		for i, v := range pt {
			if c.data[v.row][v.col] == dataFour {
				return -1, 0 // 某个方向找到终点了
			}
			if (p2.row != v.row || p2.col != v.col) && c.data[v.row][v.col] == dataTwo {
				mDir |= i // 将这个方向保存下来
				cnt++     // 方向个数+1
			}
		}
		return cnt, mDir
	}

	setNext := func(dirIn dir) {
		c.path.cur++
		c.path.path[c.path.cur-1].cnt-- // 计数-1

		tp := c.path.path[c.path.cur-1]
		tDir := tp.dir // 方向值

		var nextDir []dir
		for _, v := range []dir{up, down, left, right} {
			if dirIn&v != 0 {
				nextDir = append(nextDir, v)
			}
		}
		switch nextDir[rand.Intn(len(nextDir))] { // 随机选一个方向
		case up: // 上
			c.path.path[c.path.cur].row = tp.row - 1
			c.path.path[c.path.cur].col = tp.col
			tDir &= ^up // 去除上方向
		case down: // 下
			c.path.path[c.path.cur].row = tp.row + 1
			c.path.path[c.path.cur].col = tp.col
			tDir &= ^down // 去除下方向
		case left: // 左
			c.path.path[c.path.cur].row = tp.row
			c.path.path[c.path.cur].col = tp.col - 1
			tDir &= ^left // 去除左方向
		case right: // 右
			c.path.path[c.path.cur].row = tp.row
			c.path.path[c.path.cur].col = tp.col + 1
			tDir &= ^right // 去除右方向
		}
		c.path.path[c.path.cur-1].dir = tDir
	}

	c.path.cur = 0 // c.path缓存迷宫路径
	c.path.path[c.path.cur].row = c.start.row
	c.path.path[c.path.cur].col = c.start.col
	for { // 通过一次次尝试往下一个方向前进,直到找到解为之
		c.path.path[c.path.cur].cnt, c.path.path[c.path.cur].dir = findDir(c.path.cur)
		if c.path.path[c.path.cur].cnt < 0 {
			break // 找到结束位置
		}
		if c.path.path[c.path.cur].cnt == 0 { // 当前位置没有可以走的下一个方向
			for { // 退后直到遇到有下一个方向的位置
				if c.path.cur--; c.path.path[c.path.cur].cnt > 0 {
					break
				}
			}
		}
		setNext(c.path.path[c.path.cur].dir) // 随机选一个往下的方向走
	}

	for i := 1; i <= c.path.cur; i++ { // 将迷宫解的路径写上值
		c.data[c.path.path[i].row][c.path.path[i].col] = dataFive
	}
	c.writeDataPng(outPng)
}

// 主路扭曲,用于方案一和三
func (c *labyrinth) createPlan0or2() {
	c.start.row = c.row - 2                // 起点找最后一行
	c.start.col = rand.Intn(c.col/2)*2 + 1 // 随机一个奇数列

	c.path.path[c.path.cur].row = c.start.row
	c.path.path[c.path.cur].col = c.start.col
	c.path.cur++                                 // 记录起点
	c.data[c.start.row][c.start.col] = dataThree // 标记起点位置

	// 随机返回当前点可以前进的下个方向
	aroundPot := func(p pot) dir {
		var dir []dir
		if p.row-2 >= 0 && c.data[p.row-1][p.col] == dataZero && c.data[p.row-2][p.col] == dataOne { // 上
			dir = append(dir, up)
		}
		if p.row+2 < c.row && c.data[p.row+1][p.col] == dataZero && c.data[p.row+2][p.col] == dataOne { // 下
			dir = append(dir, down)
		}
		if p.col-2 >= 0 && c.data[p.row][p.col-1] == dataZero && c.data[p.row][p.col-2] == dataOne { // 左
			dir = append(dir, left)
		}
		if p.col+2 < c.col && c.data[p.row][p.col+1] == dataZero && c.data[p.row][p.col+2] == dataOne { // 右
			dir = append(dir, right)
		}
		if len(dir) > 0 { // 随机返回一个方向
			return dir[rand.Intn(len(dir))]
		}
		return -1
	}

	maxPath := -1
	for c.path.cur > 0 {
		switch now := c.path.path[c.path.cur-1]; aroundPot(now) {
		case up: // 上
			c.data[now.row-1][now.col] = dataTwo
			c.data[now.row-2][now.col] = dataTwo
			c.path.path[c.path.cur].row = now.row - 2
			c.path.path[c.path.cur].col = now.col
			c.path.cur++
		case down: // 下
			c.data[now.row+1][now.col] = dataTwo
			c.data[now.row+2][now.col] = dataTwo
			c.path.path[c.path.cur].row = now.row + 2
			c.path.path[c.path.cur].col = now.col
			c.path.cur++
		case left: // 左
			c.data[now.row][now.col-1] = dataTwo
			c.data[now.row][now.col-2] = dataTwo
			c.path.path[c.path.cur].row = now.row
			c.path.path[c.path.cur].col = now.col - 2
			c.path.cur++
		case right: // 右
			c.data[now.row][now.col+1] = dataTwo
			c.data[now.row][now.col+2] = dataTwo
			c.path.path[c.path.cur].row = now.row
			c.path.path[c.path.cur].col = now.col + 2
			c.path.cur++
		default: // 没有可连接的位置
			c.path.cur--
		}
		if maxPath < c.path.cur {
			maxPath = c.path.cur
		}
	}
	maxPath-- // 标记终点位置,为找到的最长路径的点作为结束点
	c.end.row, c.end.col = c.path.path[maxPath].row, c.path.path[maxPath].col
	c.data[c.end.row][c.end.col] = dataFour
}

// 方案一:主路扭曲型
func (c *labyrinth) createPlan0(outPng string) {
	c.initPlan1()      // 初始化数据
	c.createPlan0or2() // 主路扭曲
	c.writeDataPng(outPng)
}

// 方案一:自然分岔型
func (c *labyrinth) createPlan1(outPng string) {
	c.initPlan1()                        // 初始化数据
	c.data[c.start.row][c.start.col] = 2 // 将起点标记为已找过

	findBlue := func(p pot) {
		if p.row-2 >= 0 && c.data[p.row-1][p.col] == dataZero { // 上
			c.path.path[c.path.cur].row = p.row - 1
			c.path.path[c.path.cur].col = p.col
			c.path.cur++
		}
		if p.row+2 < c.row && c.data[p.row+1][p.col] == dataZero { // 下
			c.path.path[c.path.cur].row = p.row + 1
			c.path.path[c.path.cur].col = p.col
			c.path.cur++
		}
		if p.col-2 >= 0 && c.data[p.row][p.col-1] == dataZero { // 左
			c.path.path[c.path.cur].row = p.row
			c.path.path[c.path.cur].col = p.col - 1
			c.path.cur++
		}
		if p.col+2 < c.col && c.data[p.row][p.col+1] == dataZero { // 右
			c.path.path[c.path.cur].row = p.row
			c.path.path[c.path.cur].col = p.col + 1
			c.path.cur++
		}
	}

	findTwo := func(pos pot) *pot { // 返回下一个需要找周围蓝色的点
		rp := &pot{}
		if c.data[pos.row-1][pos.col] == dataTwo && c.data[pos.row+1][pos.col] == dataOne {
			rp.row, rp.col = pos.row+1, pos.col
		} else if c.data[pos.row+1][pos.col] == dataTwo && c.data[pos.row-1][pos.col] == dataOne {
			rp.row, rp.col = pos.row-1, pos.col
		} else if c.data[pos.row][pos.col-1] == dataTwo && c.data[pos.row][pos.col+1] == dataOne {
			rp.row, rp.col = pos.row, pos.col+1
		} else if c.data[pos.row][pos.col+1] == dataTwo && c.data[pos.row][pos.col-1] == dataOne {
			rp.row, rp.col = pos.row, pos.col-1
		} else {
			return nil
		}
		c.data[pos.row][pos.col] = dataTwo
		c.data[rp.row][rp.col] = dataTwo
		return rp
	}

	findOneDir := func(p pot) bool {
		cntDir := 0
		if c.data[p.row-1][p.col] == dataTwo { //上
			cntDir++
		}
		if c.data[p.row+1][p.col] == dataTwo { // 下
			cntDir++
		}
		if c.data[p.row][p.col-1] == dataTwo { // 左
			cntDir++
		}
		if c.data[p.row][p.col+1] == dataTwo { // 右
			cntDir++
		}
		return cntDir == 1 // 只有一个方向可走
	}

	nowPot := &pot{row: c.start.row, col: c.start.col}
	for c.path.cur > 0 || nowPot != nil { // 无点可找
		if nowPot != nil {
			findBlue(*nowPot)
		}

		pos := rand.Intn(c.path.cur)       // 在蓝色点中随机选一个
		nowPot = findTwo(c.path.path[pos]) // 找到2的另一个方向的1
		for pos++; pos < c.path.cur; pos++ {
			c.path.path[pos-1].row = c.path.path[pos].row
			c.path.path[pos-1].col = c.path.path[pos].col
		} // 从c.path.path中移除pos位置的数据
		c.path.cur--
	}

	var tmpStart []pot // 在最底边随机找一个起始点
	nowPot = &pot{row: c.row - 2}
	for nowPot.col = 0; nowPot.col < c.col; nowPot.col++ {
		if c.data[nowPot.row][nowPot.col] > dataZero && findOneDir(*nowPot) {
			tmpStart = append(tmpStart, *nowPot)
		}
	}

	var tmpEnd []pot // 在最顶边随机找一个结束点
	nowPot.row = 1
	for nowPot.col = 0; nowPot.col < c.col; nowPot.col++ {
		if c.data[nowPot.row][nowPot.col] > dataZero && findOneDir(*nowPot) {
			tmpEnd = append(tmpEnd, *nowPot)
		}
	}
	is, ie := rand.Intn(len(tmpStart)), rand.Intn(len(tmpEnd))
	c.start.row, c.start.col = tmpStart[is].row, tmpStart[is].col
	c.end.row, c.end.col = tmpEnd[ie].row, tmpEnd[ie].col

	c.data[c.start.row][c.start.col] = dataThree
	c.data[c.end.row][c.end.col] = dataFour
	c.writeDataPng(outPng)
}

// 方案三:块状分割型
// 写起来蛋疼,执行后效果也不太理想,因为出来的图很容易找到出路
// 而且通过算法找到的路径很多重合,懒得优化了
func (c *labyrinth) createPlan2(outPng string) {
	c.initPlan2() // 初始化数据
	c.createPlan0or2()

	// 连接块状区域
	for i := 1; i < c.row; i += 2 {
		for j := 1; j < c.col; j += 2 {
			if c.data[i][j] == dataSix { // 找到一个块状左上顶点
				w, h := j+1, i+1
				for c.data[i][w] == dataSix {
					w++
				}
				for c.data[h][j] == dataSix {
					h++
				} // 获取橙色1区域宽高

				ppUp := make([]int, 0, w-j)
				ppDown := make([]int, 0, w-j)
				for k := j; k < w; k++ {
					if c.data[i-2][k] == dataTwo && c.data[i][k] == dataSix {
						ppUp = append(ppUp, k)
					}
					if c.data[h+1][k] == dataTwo && c.data[h-1][k] == dataSix {
						ppDown = append(ppDown, k)
					}
				}
				if len(ppUp) > 0 { // 随机连接上面一边
					c.data[i-1][ppUp[rand.Intn(len(ppUp))]] = dataTwo
				}
				if len(ppDown) > 0 { // 随机连接下面一边
					c.data[h][ppDown[rand.Intn(len(ppDown))]] = dataTwo
				}

				ppLeft := make([]int, 0, h-i)
				ppRight := make([]int, 0, h-i)
				for k := i; k < h; k++ {
					if c.data[k][j-2] == dataTwo && c.data[k][j] == dataSix {
						ppLeft = append(ppLeft, k)
					}
					if c.data[k][w+1] == dataTwo && c.data[k][w-1] == dataSix {
						ppRight = append(ppRight, k)
					}
				}
				if len(ppLeft) > 0 { // 随机连接上面一边
					c.data[ppLeft[rand.Intn(len(ppLeft))]][j-1] = dataTwo
				}
				if len(ppDown) > 0 { // 随机连接下面一边
					c.data[ppRight[rand.Intn(len(ppRight))]][w] = dataTwo
				}
				// 将橙色1变为普通道路
				for ih := i; ih < h; ih++ {
					for iw := j; iw < w; iw++ {
						c.data[ih][iw] = dataTwo
					}
				}
			}
		}
	}
	c.writeDataPng(outPng)
}
